/**
 * RadialInterpolator.java
 * colourmap
 * Copyright (C) 2010 Alan W.F. Boyd
 * This program is free software: you can redistribute it and/or modify
 * it under the terms of the GNU General Public License as published by
 * the Free Software Foundation, either version 3 of the License, or
 * (at your option) any later version.
 * 
 * This program is distributed in the hope that it will be useful,
 * but WITHOUT ANY WARRANTY; without even the implied warranty of
 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
 * GNU General Public License for more details.
 * 
 * You should have received a copy of the GNU General Public License
 * along with this program.  If not, see <http://www.gnu.org/licenses/>.
 * 
 * You can contact the author via the google code web page for the project
 * <http://colourmap.googlecode.com>
 */
package com.googlecode.colourmap.interpolator;

import java.util.HashMap;
import java.util.Iterator;

import com.googlecode.colourmap.Point;


/**
 * This class interpolates the value of a point (p) by using a radial method.
 * All known points within a fixed radius of p are weighted according to their distance from p to determine the
 * value of p.
 * 
 * The radius is incrementally calculated to be as small as possible such that some minimum number of nodes (4)
 * are contained within the radius.
 * 
 * @author Alan W.F. Boyd
 *
 */
public class RadialInterpolator implements IInterpolator
{
	/** Specifies the number of points to use in calculating an unknown (other) point */
	private static final int IDEAL_POINTS = 4;
	
	/** The known points from the data file */
	private HashMap<Point, Float> knownPoints = new HashMap<Point, Float>();
	
	/** The maximum distance between any pair of known points */
	private int maxRadius = Integer.MIN_VALUE;
	
	/**
	 * Provides the value for a point, using the known points from the data set
	 * @param c the point for which a value is required
	 * @return the value of that point, calculated according to the distance and values of other nearby known points
	 */
	public Float getValue(Point c)
	{
		// Find the ideal points, i.e. the nearest (max 4)
		int idealRadius = findIdealRadius(c);
		HashMap<Point, Float> interestedPoints = pointsInRange(idealRadius, c);
		
		// Add their total distances (x) away from the point
		float totalDistance = 0;
		Iterator<Point> i = interestedPoints.keySet().iterator();
		while (i.hasNext())
			totalDistance += i.next().distance(c);

		// If an ideal point is a distance of 0 from c, then it returns the value of that point.
		// Otherwise, the value of point c is weighted based on the distance of each ideal point from c.
		// Closer points are weighted more highly.
		
		float totalWeightedValue = 0;
		float totalWeightings = 0;
		
		i = interestedPoints.keySet().iterator();
		while (i.hasNext())
		{
			Point thisPoint = i.next();
			double thisPointDistance = thisPoint.distance(c);
			
			if (thisPointDistance <= 0)
				return interestedPoints.get(thisPoint);
			
			// Nearer points are weighted more heavily
			totalWeightings += (totalDistance / thisPointDistance);
			
			// Perform the weighting by adding the contributing factors. The average will occur at the end
			totalWeightedValue += (totalDistance / thisPointDistance) * interestedPoints.get(thisPoint); 
		}
		
		// Complete the weighting
		return totalWeightedValue / totalWeightings;
	}

	/**
	 * Specifies the set of known points from the data set
	 * @param p a mapping of points and values from the data set
	 */
	public void setPoints(HashMap<Point, Float> p)
	{
		knownPoints.putAll(p);
		
		Iterator<Point> i = knownPoints.keySet().iterator();
		while (i.hasNext())
		{
			Point c = i.next();
			
			Iterator<Point> j = knownPoints.keySet().iterator();
			while (j.hasNext())
			{
				Point d = j.next();
				int radius = (int)c.distance(d);
				
				if (radius > maxRadius)
					maxRadius = radius;
			}
		}
	}

	/**
	 * Finds the radius that encompasses IDEAL_POINTS nodes
	 * @param c the centre point of the radius
	 * @return the size of radius that encompasses the required number of points
	 */
	private int findIdealRadius(Point c)
	{
		int lowest = 1;
		int highest = maxRadius;
		int attempt = lowest;
		
		while (lowest < highest)
		{
			attempt = (lowest + highest)/2;
			int numInRange = numInRange(attempt, c);
			
			if (numInRange < IDEAL_POINTS)
				lowest = attempt + 1;
			else if (numInRange > IDEAL_POINTS)
				highest = attempt - 1;
			else
				return attempt;
		}
		
		return attempt;
	}
	
	/**
	 * Determines the set of points within a given radius of a given point
	 * @param radius the radius to use
	 * @param c the given point
	 * @return the set of points within the given distance of the given point
	 */
	private HashMap<Point, Float> pointsInRange(int radius, Point c)
	{
		HashMap<Point, Float> result = new HashMap<Point, Float>();

		Iterator<Point> i = knownPoints.keySet().iterator();
		while (i.hasNext())
		{
			Point d = i.next();
			if (c.distance(d) <= radius)
				result.put(d, knownPoints.get(d));
		}
		
		return result;
	}
	
	/**
	 * Number of points within a certain radius of a given point
	 * @param radius the radius to use
	 * @param c the given point
	 * @return the number of points within the given distance of the given point
	 */
	private int numInRange(int radius, Point c)
	{
		int numInRange = 0;
		
		Iterator<Point> i = knownPoints.keySet().iterator();
		while (i.hasNext())
		{
			Point d = i.next();
			if (c.distance(d) <= radius)
				numInRange++;
		}
		
		return numInRange;
	}
}
